package ga;

public class GA {

    /* GA parameters */
    private static final double mutationRate = 0.05;
    private static final int tournamentSize = 10;

    // Evolves a population over one generation
    public static Population evolvePopulation(Population pop) {
        Population newPopulation = new Population(pop.populationSize(), false);
        
        // Adding fittest path from previous evolution
        newPopulation.savePath(0, pop.getFittest());
        int offset = 1;
        

        // Creating new population by adding new paths through tournament 
        // selection and crossover
        for (int i = offset; i < newPopulation.populationSize(); i++) {
            
            Path parent1 = tournamentSelection(pop);
            Path parent2 = tournamentSelection(pop);

            Path child = crossover(parent1, parent2);
            
            newPopulation.savePath(i, child);
        }

        // Mutate the new population to add some new genetic material
        for (int i = offset; i < newPopulation.populationSize(); i++) {
            mutate(newPopulation.getPath(i));
        }

        return newPopulation;
    }

    // Applies crossover to a set of parents and creates offspring
    public static Path crossover(Path parent1, Path parent2) {

    	Path child = new Path();

        // Randomly chosen start and end position of parent1 
        int startPos = (int) (Math.random() * parent1.pathSize());
        int endPos = (int) (Math.random() * parent1.pathSize());

        // Adding the sub-path specified by random indexes to the child path
        for (int i = 0; i < child.pathSize(); i++) {
            if (startPos < endPos && i > startPos && i < endPos) {
                child.setPoint(i, parent1.getPoint(i));
            } else if (startPos > endPos) {
                if (!(i < startPos && i > endPos)) {
                    child.setPoint(i, parent1.getPoint(i));
                }
            }
        }

        for (int i = 0; i < parent2.pathSize(); i++) {
            // If child doesn't have specific point on the path we add it
            if (!child.containsPoint(parent2.getPoint(i))) {
                // Put this point to the first empty slot of the child path
                for (int j = 0; j < child.pathSize(); j++) {
                    if (child.getPoint(j) == null) {
                        child.setPoint(j, parent2.getPoint(i));
                        break;
                    }
                }
            }
        }
        return child;
    }

    // Mutate a tour using swap mutation
    private static void mutate(Path path) {
        for(int i = 0; i < path.pathSize(); i++){
            if(Math.random() < mutationRate){
                // Get a second position in the path
                int j = (int) (path.pathSize() * Math.random());

                Point pointToSwap1 = path.getPoint(i);
                Point pointToSwap2 = path.getPoint(j);

                // Swap points
                path.setPoint(j, pointToSwap1);
                path.setPoint(i, pointToSwap2);
            }
        }
    }

    // Selects the fittest path from random candidate paths
    private static Path tournamentSelection(Population pop) {
        Population tournament = new Population(tournamentSize, false);
        // Adds random candidate path to tournament selection
        for (int i = 0; i < tournamentSize; i++) {
            int randomId = (int) (Math.random() * pop.populationSize());
            tournament.savePath(i, pop.getPath(randomId));
        }
        // Get the fittest path from selction
        Path fittest = tournament.getFittest();
        return fittest;
    }
}